package master;

import java.util.ArrayList;
import java.util.List;

/**
 * @author chenyw
 * @date 2022/9/13 19:30
 *
 * 多数元素II:
 * 解题关键：一个数组中最多只会有两个大于数组三分之一的元素
 */
public class M229majorityElement {
    public List<Integer> majorityElement(int[] nums) {
        int e1 = 0;
        int e2 = 0;
        int v1 = 0;
        int v2 = 0;
        for (int num : nums) {
            if (v1 > 0 && e1 == num) {
                v1++;
            } else if (v2 > 0 && e2 == num) {
                v2++;
            } else if (v1 == 0) {
                v1++;
                e1 = num;
            } else if (v2 == 0) {
                v2++;
                e2 = num;
            } else {
                v1--;
                v2--;
            }
        }
        int count1 = 0;
        int count2 = 0;
        //判断是否大于三分之一
        for (int num : nums) {
            if (num == e1) {
                count1++;
            }
            if (num == e2 && e2 != e1) {
                count2++;
            }
        }
        List<Integer> list = new ArrayList<>();
        if (count1 > nums.length / 3) {
            list.add(e1);
        }
        if (count2 > nums.length / 3) {
            list.add(e2);
        }
        return list;
    }
}
